494. 目标和
494. 目标和
分析
这道题有点困难。我一开始没想到思路，但是后面找到了正确的 dp 的定义，然后就很顺了。
首先因为数组的所有成员都是非负数，所以只要做过 416. 分割等和子集 大概就是知道，这个操作其实是把整个数组的数字分成两拨，然后用一波的和减去另一波的和，得到的差值是 target，这个其实是在求从数组中找出一些数字，这些数字的和为 (sum+target)/2，典型的背包问题。
但是，题目中要我们求的，其实是两拨数字的和差值等于 target 的不同表达式的数目。注意求的是数目，而不是最大值。
背包问题-01背包 中，我们求的是将多个物品放入有限容量的背包中，物品的总价值的最大值是多少。而这个题，求的是，将多个物品放入指定容量的背包中，刚好把背包填满，有多少种填法。
这里我们就不能直接套 背包问题-01背包 的模板了，我们得重新想定义 dp 数组。
我们在之前做动态规划的时候的经验就是，直接根据最终要求出的数字的定义来定义 dp 数组，比如 343. 整数拆分，这里我们也是这样做。
定义 dp[j] 为将多个物品塞到容量为 j 的背包中刚好塞满的方式的个数。
然后状态转移方程我们也可以参考 背包问题-01背包 的推导方法，判断将 nums[0] 到 nums[i] 刚好塞满容量为 j 的背包只有两种方式，一种是放 nums[i] ，一种是不放 nums[i]，dp[j] 的值，为这两种方式的和，不放 nums[i] 的时候，方式的个数其实就是 dp[i-1][j] 的值（在一维 dp 数组里就是 dp[j]），放 nums[i] 的时候，方式的个数其实就是 dp[i-1][j-nums[i]] 的值（在一维 dp 数组里就是 dp[j-nums[i]]）。所以 dp 数组的状态转移方程就是 dp[j] = dp[j] + dp[j-nums[i]];。
很容易犯错的地方是初始化。根据 dp 数组的定义，dp[0] 应该是多少，
答案是 1，因为将物品放到容量为 0 的背包里，有多少种方式？什么都不放，也是一种方式。
一维 dp 数组的遍历方式，跟 背包问题-01背包#优化 一样，外层遍历物品，内层遍历背包容量，容量是从大到小遍历，遍历到 nums[i] 为之。这里就不赘述了。
还有一个注意点，就是 target 可能为负数，取绝对值了之后再用，
而且如果 (sum+target)/2 有余数，即 (sum+target)%2!=0，则说明也是无法分成两拨，且两拨的和的差值为 target 的。此时可直接返回 0。
而且如果 target 的绝对值大于 sum，那也是无法实现的，也需要直接返回 0。
以上过程是我自己的思维过程，具体的详细的推导过程，看 代码随想录二维 dp，代码随想录一维 dp
这个题跟 39. 组合总和 很像，我看到本题的时候，脑子里闪过的也是组合，但是 39. 组合总和 是要求我们把所有的组合的情况求出来，而不仅仅是求出组合的个数，所以还是只能用回溯算法来做。
解题
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int num:nums){
sum += num;
}
// target 有可能是负数
target = Math.abs(target);
// target 大于 sum，无解
if(target>sum){
return 0;
}
//sum+target 不能整除，无解
if((sum+target)%2!=0){
return 0;
}
int targetSize = (sum+target)/2;
int[] dp = new int[targetSize+1];
// 注意 dp[0]什么都不放，也是一种方式，
// 这跟把价值为0的元素放进去，不同。
dp[0]=1;
for(int i=0;i<nums.length;i++){
for(int j=targetSize;j>=nums[i];j--){
dp[j] = dp[j]+dp[j-nums[i]];
}
}
return dp[targetSize];
}